/*
 * @lc app=leetcode.cn id=1345 lang=cpp
 *
 * [1345] 跳跃游戏 IV
 */

// @lc code=start
class Solution
{
public:
    typedef pair<int, int> PII;

    int minJumps(vector<int> &arr)
    {
        unordered_map<int, vector<int>> idxSameVal;
        int n = arr.size();
        for (int i = 0; i < n; i++)
        {
            idxSameVal[arr[i]].push_back(i);
        }

        unordered_set<int> visited;
        queue<PII> q;
        visited.emplace(0);
        q.push(PII(0, 0));

        while (!q.empty())
        {
            auto [idx, step] = q.front();
            q.pop();

            if (idx == n - 1)
            {
                return step;
            }

            step++;

            int val = arr[idx];
            if (idxSameVal.count(val))
            {
                for (int i : idxSameVal[val])
                {
                    if (visited.count(i))
                    {
                        continue;
                    }
                    visited.emplace(i);
                    q.push(PII(i, step));
                }
                idxSameVal.erase(val);
            };

            if (idx + 1 < n && !visited.count(idx + 1))
            {
                visited.emplace(idx + 1);
                q.push(PII(idx + 1, step));
            };

            if (idx - 1 >= 0 && !visited.count(idx - 1))
            {
                visited.emplace(idx - 1);
                q.push(PII(idx - 1, step));
            };
        }

        return -1;
    }
};
// @lc code=end
